package com.ma.dp.demo;

/**
 * @ClassName Knapsack01
 * @Author: mayongqiang
 * @DATE 2022/4/9 11:51
 * @Description: 0-1背包问题
 */
/*
动态规划的大体框架：
    ```
    for 状态1 in 状态1的所有取值
        for 状态2 in 状态2的所有取值
            for ....
                dp[状态1][状态2][..] = 择优[选择1，选择2.......]
    ```
*/
public class Knapsack01 {
    public static void main(String[] args) {
        System.out.println(knapsack(3, 4, new int[]{2, 1, 3}, new int[]{4, 2, 3}));
    }

    /*
    给你一个可装载重量w的背包和N个物品,每个物品有重量wt和价值val两个属性
    用这个背包装物品,最多能装的价值是多少？
    eg:  input: N = 3 , W = 4 , wt = [2,1,3] , val = [4,2,3];    return 6;
     */
    static int knapsack(int n, int w, int[] wt, int[] val) {

        /*
        一、明确状态和选择  状态也就是一个问题的局面
         状态有两个 : 1、背包的容量  2、可选择的物品
         选择 : 装进背包/不装进背包
        二、明确dp数组的含义   dp数组就是描述问题局面的一个数组
           dp数组来描述状态 状态有两个----->二维数组描述
                        dp[i][w]  对于前i个物品,当前背包容量为w时能装下的最大价值
                        dp[3][5] = 6 代表只对前三个物品做选择,背包容量为5时 最多能放下的价值为6
        三、base case
            dp[0][..] = 0   dp[..][0] = 0   dp[N][W]就是最终状态

        套入框架
            ```
            int dp[N+1][M+1]
            dp[0][] = 0
            dp[][0] = 0
            for i in range [1..N]：
                for j in range[1..M]：
                    dp[i][w] = max(
                        将i放入背包
                        不将i放入背包
                        )
            return dp[N][W]
            ```
        四、状态转移方程
            针对两种选择
                1、将i放入背包    dp[i][w] = dp[i - 1][w - wt[i-1]] + val[i - 1]
                                        = 不装i时能装的最大价值 + i的价值
                                        = 所以应该求剩余重量 w-wt[i-1]能装的最大价值
                2、不将i放入背包  dp[i][2] = dp[i-1][w]
        五、补充
            if(w-wt[i-1]<0):
                装不下 dp[i][w] = dp[i-1][w];
            else:
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i - 1], dp[i-1][w]);

        */
        int[][] dp = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w; j++) {
                if (j - wt[i - 1] < 0) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][w];
    }
}
